﻿// From: http://stackoverflow.com/questions/380595/multimap-in-net
//////////////////////////////////////////////////////////////////////
// Algorithmia is (c) 2008 Solutions Design. All rights reserved.
// http://www.sd.nl
//////////////////////////////////////////////////////////////////////
// COPYRIGHTS:
// Copyright (c) 2008 Solutions Design. All rights reserved.
// 
// The Algorithmia library sourcecode and its accompanying tools, tests and support code
// are released under the following license: (BSD2)
// ----------------------------------------------------------------------
// Redistribution and use in source and binary forms, with or without modification, 
// are permitted provided that the following conditions are met: 
//
// 1) Redistributions of source code must retain the above copyright notice, this list of 
//    conditions and the following disclaimer. 
// 2) Redistributions in binary form must reproduce the above copyright notice, this list of 
//    conditions and the following disclaimer in the documentation and/or other materials 
//    provided with the distribution. 
// 
// THIS SOFTWARE IS PROVIDED BY SOLUTIONS DESIGN ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SOLUTIONS DESIGN OR CONTRIBUTORS BE LIABLE FOR 
// ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 
// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 
// BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 
// USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
//
// The views and conclusions contained in the software and documentation are those of the authors 
// and should not be interpreted as representing official policies, either expressed or implied, 
// of Solutions Design. 
//
//////////////////////////////////////////////////////////////////////
// Contributers to the code:
//      - Frans  Bouma [FB]
//      - Daniel Perelman (modified to use SortedSet)
//////////////////////////////////////////////////////////////////////
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Util;

namespace SD.Tools.Algorithmia.GeneralDataStructures
{
    // From http://stackoverflow.com/questions/1916814/c-sharp-need-an-idictionary-implementation-that-will-allow-a-null-key
    public class NullableDictionary<K, V> : IDictionary<K, V> where K:class
    {
        private Dictionary<K, V> data = new Dictionary<K, V>();
        private V null_value;
        private bool null_value_set = false;

        public void Add(K key, V value)
        {
            this[key] = value;
        }
        public void Add(KeyValuePair<K, V> item)
        {
            this[item.Key] = item.Value;
        }
        public virtual bool Remove(K key)
        {
            if (key == null)
            {
                bool res = null_value_set;
                null_value_set = false;
                null_value = default(V);
                return null_value_set;
            }
            else
            {
                return data.Remove(key);
            }
        }

        public virtual V this[K key]
        {
            get
            {
                if (key == null)
                { return null_value; }
                return data[key];
            }
            set
            {
                if (key == null)
                { null_value = value; null_value_set = true; }
                else
                { data[key] = value; }
            }
        }

        public virtual bool TryGetValue(K key, out V value)
        {
            if (key == null)
            {
                value = null_value;
                return null_value_set;
            }
            else
            {
                return data.TryGetValue(key, out value);
            }
        }

        bool IDictionary<K, V>.ContainsKey(K key)
        {
            if (key == null)
            {
                return null_value_set;
            }
            else
            {
                return data.ContainsKey(key);
            }
        }

        ICollection<K> IDictionary<K, V>.Keys
        {
            get
            {
                IEnumerable<K> res = data.Keys;
                if (null_value_set)
                {
                    res = EnumerableUtil.Cons(null, res);
                }
                return res.ToList();
            }
        }

        public ICollection<V> Values
        {
            get
            {
                IEnumerable<V> res = data.Values;
                if (null_value_set)
                {
                    res = EnumerableUtil.Cons(null_value, res);
                }
                return res.ToList();
            }
        }

        void ICollection<KeyValuePair<K, V>>.Clear()
        {
            this.Remove(null);
            data.Clear();
        }

        bool ICollection<KeyValuePair<K, V>>.Contains(KeyValuePair<K, V> item)
        {
            return this[item.Key].Equals(item.Value);
        }

        void ICollection<KeyValuePair<K, V>>.CopyTo(KeyValuePair<K, V>[] array, int arrayIndex)
        {
            foreach (var kv in this)
            {
                array[arrayIndex++] = kv;
            }
        }

        // int ICollection<KeyValuePair<K, V>>.Count
        public int Count
        {
            get { return data.Count + (null_value_set ? 1 : 0); }
        }

        bool ICollection<KeyValuePair<K, V>>.IsReadOnly
        {
            get { return false; }
        }

        bool ICollection<KeyValuePair<K, V>>.Remove(KeyValuePair<K, V> item)
        {
            if (this.Contains(item))
            {
                return this.Remove(item.Key);
            }
            return false;
        }

        IEnumerator<KeyValuePair<K, V>> IEnumerable<KeyValuePair<K, V>>.GetEnumerator()
        {
            IEnumerable<KeyValuePair<K, V>> res = data;
            if (null_value_set)
            {
                res = EnumerableUtil.Cons(
                    new KeyValuePair<K, V>(null, null_value), res);
            }
            return res.GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<KeyValuePair<K, V>>)this).GetEnumerator();
        }
    }

    /// <summary>
    /// Extension to the normal Dictionary. This class can store more than one value for every key. It keeps a HashSet for every Key value.
    /// Calling Add with the same Key and multiple values will store each value under the same Key in the Dictionary. Obtaining the values
    /// for a Key will return the SortedSet with the Values of the Key. 
    /// </summary>
    /// <typeparam name="TKey">The type of the key.</typeparam>
    /// <typeparam name="TValue">The type of the value.</typeparam>
    public class MultiValueDictionary<TKey, TValue> : NullableDictionary<TKey, SortedSet<TValue>> where TKey:class
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="MultiValueDictionary&lt;TKey, TValue&gt;"/> class.
        /// </summary>
        public MultiValueDictionary()
            : base()
        {
        }


        /// <summary>
        /// Adds the specified value under the specified key
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="value">The value.</param>
        public void Add(TKey key, TValue value)
        {
            SortedSet<TValue> container = null;
            if (!this.TryGetValue(key, out container))
            {
                container = new SortedSet<TValue>();
                base.Add(key, container);
            }
            container.Add(value);
        }


        /// <summary>
        /// Determines whether this dictionary contains the specified value for the specified key 
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="value">The value.</param>
        /// <returns>true if the value is stored for the specified key in this dictionary, false otherwise</returns>
        public bool ContainsValue(TKey key, TValue value)
        {
            bool toReturn = false;
            SortedSet<TValue> values = null;
            if (this.TryGetValue(key, out values))
            {
                toReturn = values.Contains(value);
            }
            return toReturn;
        }


        /// <summary>
        /// Removes the specified value for the specified key. It will leave the key in the dictionary.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="value">The value.</param>
        public void Remove(TKey key, TValue value)
        {
            SortedSet<TValue> container = null;
            if (this.TryGetValue(key, out container))
            {
                container.Remove(value);
                if (container.Count <= 0)
                {
                    this.Remove(key);
                }
            }
        }


        /// <summary>
        /// Merges the specified multivaluedictionary into this instance.
        /// </summary>
        /// <param name="toMergeWith">To merge with.</param>
        public void Merge(MultiValueDictionary<TKey, TValue> toMergeWith)
        {
            if (toMergeWith == null)
            {
                return;
            }

            foreach (KeyValuePair<TKey, SortedSet<TValue>> pair in toMergeWith)
            {
                foreach (TValue value in pair.Value)
                {
                    this.Add(pair.Key, value);
                }
            }
        }


        /// <summary>
        /// Gets the values for the key specified. This method is useful if you want to avoid an exception for key value retrieval and you can't use TryGetValue
        /// (e.g. in lambdas)
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="returnEmptySet">if set to true and the key isn't found, an empty hashset is returned, otherwise, if the key isn't found, null is returned</param>
        /// <returns>
        /// This method will return null (or an empty set if returnEmptySet is true) if the key wasn't found, or
        /// the values if key was found.
        /// </returns>
        public SortedSet<TValue> GetValues(TKey key, bool returnEmptySet)
        {
            SortedSet<TValue> toReturn = null;
            if (!base.TryGetValue(key, out toReturn) && returnEmptySet)
            {
                toReturn = new SortedSet<TValue>();
            }
            return toReturn;
        }
    }
}